1424J - Lonely Numbers - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"


const int N=1000001;
int ans[N];
int isp[N];

main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    ans[1]=1;
    for(int i=2;i<N;i++){
        if(isp[i]==0){
            ans[i]++;
            if(i<=sqrtl(N)){
                ans[i*i]--;
                for(int j=i*i;j<N;j+=i) isp[j]=1;
            }
        }
        ans[i]+=ans[i-1];
    }
    
	int t,n;
	cin>>t;
	while(t--){
	    cin>>n;
	    cout<<ans[n]<<endl;
	}
	return 0;
}